Modem computer systems are increasingly being used to solve difficult problems in the real physical world. In computer systems, physical items, or representations of virtual items are stored in memories as data structures. Machine executable instructions manipulate the data to solve optimization problems. Increasingly, the structures and problems are becoming more complex.
For example, computers are frequently used to process images. There, the photons of the physical world are converted to pixels at fixed coordinates, each pixel representing variable light intensity and color values. Optimally manipulating millions of pixels requires a large amount of processing, therefore, quickly finding optimal solutions is an important task for computer scientists and engineers.
In the prior art, techniques for finding optimal solutions to problems posed as linear data structures, such as the images in the example above, e.g., independent variables expressed as vectors, are well know. The vectors, perhaps, describe measurable physical attributes associated with the pixels, i.e., intensity and color. Generally, the time and the location of the pixels are ordered in the memories according to a Cartesian coordinate system.
There, optimization techniques for image registration or motion analysis problems, may focus on reducing the total "distance" between the vectors of pixels in successive image planes. Because the variables are independent and can be represented linearly, many image processing problems can be managed in real time.
However, for many complex items, the mere locations of the items is insufficient to derive an optimal solution. Instead, the relative location of the items to each other is the key element in being able to determine an optimal solution. In other words, the ordering of the items is important.
For example, in genetic analysis, the "decoding" of DNA into its functional items, e.g., genes, must take into consideration the numerous possible permutations in which the genes can be sequenced. That is, the relative ordering of the genes is a significant factor in genetic expressions.
Another difficult optimization problem, this time in the field of electronics, is how to optimally lay out the millions of electronic components on a small semiconductor chip so that signalling paths between the components is minimized in order to maximize performance. Again, here, the possible orderings or placement of electronic items (cells) are usually expressed in a permutation space or domain.
More generally and formally, optimization problems where the domains of the parameters to be optimized are described as sets of independent variables are said to belong in a Cartesian, linear, or vector space. Optimization problems where the domains of the variables depends on their order are said to belong in a permutation space.
In the case of vector spaces, the values of the variables are independent of each other, and the optimizing function can typically be geometrically represented in a space which has as many dimensions as there are variables.
For example, a two variable function F(x,y) which is to be optimized in a continuous Cartesian space can be expressed as: EQU F(x,y)=(x+y).sup.4 -(x-y).sup.2
where:
x .epsilon. 0, . . . , 5! and y .epsilon. 1, . . . , 4!. PA1 x .epsilon. 1 . . . 3! and P(x)=the position of x in the permutation. PA1 Q(1,2,3)=1+4+9=14; Q(1,3,2)=1+6+6=13; PA1 Q(2,1,3)=2+2+9=13; Q(2,3,1)=2+6+3=11; PA1 Q(3,1,2)=3+2+6=11; Q(3,2,1)=3+4+3=10, and so forth, however PA1 Q(1,2,2), Q(1,1,3), Q(3,3,2), etc. are non-valid permutations since a specific item appears more than once in the order. PA1 1/2 4 7 8/3 5 6 representing a first parent, and PA1 5/2 7 4 6/3 1 8 representing a second parent, PA1 1:2 7 4 6:3 5 6 a first child permutation, and PA1 5:2 4 7 8:3 1 8 a second child permutation.
As an advantage of vector spaces, the concept of distance between objects can easily be defined, and therefore, the task to minimize the distance between items can use many different optimization techniques. For example, in a continuous vector space, a derivative function or a gradient descent technique can readily yields one or more minima.
In the case of permutation spaces, it is the order of the items which constitute the n-tupla of values that differentiates one input into the optimization from another. That is, the value of the variables in the n-tupla items at different positions are clearly dependent on each other. For example, a three variable function Q(x,y,z) described by a discrete permutation space can be expressed as: EQU Q(x,y,z)=(x.times.P(x))+(y.times.P(y))+(z.times.P(z))
where:
In this case, valid permutation of Q(x,y,z) include:
Independent of the optimization technique used, dealing with vectors of variables is generally much easier than working with permutations. Optimizations in vector spaces typically use general methodologies, whereas in permutation spaces, dedicated methods have usually been required. This means that a method for one application may be of no use in another application.
Some workarounds are known for dealing with optimization problems in permutation spaces. One popular technique uses a penalty function. There, an input sequence of values is "penalized" the "farther" it is from a permitted permutation.
For example, it is desired to minimize a given objective function F(x), where the variable x can take on any integer value in the range 1, . . . , n, . . . Moreover, the value of F(x) is restricted to be in the range: min . . . max. A possible penalty function p(x) could be expressed as: EQU p(x)=1+number of items with the same value.times.min,
with a new penalized objective function: EQU F*(x)=p(x).times.F(x).
In this case, all legal permutations still have the same old values, and illegal permutations are increasingly penalized according to the number of "wrong" items in the sequence.
In another technique, only permitted input values are generated during an iterative optimization process. For example, in methods for genetic applications, e.g., DNA analysis, special cross-over and mutation operators have been developed, or in simulated annealing techniques only swapping is allowed between items of a permutation.
For example, with genetic methods, at popular cross-over operator is the so called Partial Matched Cross-over (PMX), described by D. Goldberg in "Genetic Algorithms in Search Optimization&Machine Learning, Addison-Wesley, 1989, pp. 170-171. There, two chromosomes, one from each contributing parent are aligned, and two crossing sites are randomly selected.
The crossing sites define a matching section. The matching section identifies two genes that will be exchanged (swapped) in the chromosomes of the parents. For example, given two arbitrary DNA sequences:
with two random cross-over sites ".vertline.", the swapping of the matching sections {2 4 7 8} and {2 7 4 6} will produce:
This is an easy-to-implement order-based cross-over. Unfortunately the semantics of the operation, and its practicality depend on the specific optimization problem to be solved. In many cases, the cross-over operator is ineffective, or not applicable at all.
Although both the penalizing function and the cross-over operator each offer advantages and disadvantages, they tend to obscure the problem by adding complexities to the optimizing methods, and therefore decrease their effectiveness.
It is desired to provide a general method that allows the best optimization techniques available for problems expressed in vector spaces to also be applied to all order based problems whose domains are represented in permutation spaces. The methodology should be applicable to real physical world problems, such as, for example, the optimal placement of interconnected components or modules in a surface plane of a semiconductor die. Here, it is desired to minimize the total length of interconnecting lines in order to maximize the performance of the components.